package gitdemo1.git3.demo;

import gitdemo1.git3.day01.Person;
import org.springframework.util.CollectionUtils;

import java.io.*;
import java.util.*;

public class Demo {

    public static void main(String[] args) throws Exception{
        try {
//            new FileReader()
            FileOutputStream fos = new FileOutputStream("out.txt");
            String s="hello";
            fos.write(s.getBytes());
            fos.close();
        } catch (Exception e) {
            e.printStackTrace();
        }

    }


//    ArrayList<String> ans= new ArrayList<String>();
//    public List<String> generateParenthesis(int n) {
//        if(n<1){
//            return ans;
//        }
//        dfs("",n,n);
//        return ans;
//    }
//
//    private void dfs(String str, int left, int right) {
//        if(left==0&&right==0){
//            ans.add(str.toString());
//            return;
//        }
//        if(left==right){
//            dfs(str+"(", left-1, right);
//
//        }else if(left<right){
//            if(left>0){
//                dfs(str+"(", left-1, right);
//            }
//            dfs(str+")", left, right-1);
//        }
//    }

    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        int res=1;
        int max=0;
        int p=0;
        for (int i = 1; i < nums.length; i++) {
            if(nums[i]==nums[i-1]){
                res++;
            }else {
                res=1;
            }

            if(res>max){
                max=res;
                p=i;
            }

        }
        return nums[p];

    }

    public int maxProfit(int[] prices) {
        //贪心思想
        int max=0;
        int cur=prices[0];
        for (int price : prices) {
            if(price<cur){
                cur=price;
                continue;
            }
            if(price-cur>max){
                max=price-cur;
            }
        }
        return max;
    }


    public int hammingDistance(int x, int y) {
        int s=x^y,res=0;
        while (s>0){
            res+=s&1;
            s>>=1;
        }
        return res;

    }

    public static List<Integer> findDisappearedNumbers(int[] nums) {
        int len=nums.length;
        Arrays.sort(nums);

        ArrayList<Integer> list = new ArrayList<>();

        for (int i = 0; i < len; i++) {
            nums[i]=nums[i]+len;
        }
        for (int i = 0; i < len; i++) {
            if(nums[i]<len){
                list.add(i+1);
            }
        }


        return list;
    }

    public int[] countBits(int n) {
        int[] res = new int[n + 1];
        res[0]=0;
        for (int i = 1; i <= n; i++) {
            if(i%2==1){
                res[i]=res[i-1]+1;
            }else {
                res[i]=res[i/2];
            }

        }
        return res;

    }


    public int findMin1(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[left] > nums[right]) {
                left = mid ;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }

    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }

    public int search2(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) {
            return -1;
        }
        if (n == 1) {
            return nums[0] == target ? 0 : -1;
        }
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[n - 1]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }

    public static int search1(int[] nums, int target) {
        int left=0,right=nums.length-1;
        while (left<=right){
            int mid=left+(right-left)/2;
            if(target>nums[mid]){
                if(target>=nums[left]){
                    right=mid-1;
                }else {
                   left=mid+1;
                }
            }else if(target<nums[mid]){
                if(nums[left]<=target){
                    right=mid-1;
                }else {
                    left=mid+1;
                }
            }else {
                return mid;
            }


        }

        return -1;

    }


    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        ArrayList<List<Integer>> res = new ArrayList<>();

        int p=0;
        for (int i = 0; i < nums.length; i++) {
//            ArrayList<Integer> list = new ArrayList<>();
            if(nums[i]>=1){
                return res;
            }
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            int left=i+1;
            int right=nums.length-1;
            int ans=0-nums[i];
            while(left<right){

                if(nums[left]+nums[right]>ans){
                    right--;
                }else if(nums[left]+nums[right]<ans){
                    left++;
                }else {

                    res.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;
                    right--;
                    left++;
                }

            }
        }

        return res;

    }

    public int[] searchRange(int[] nums, int target) {

        int[] res = new int[2];
        res[0]=-1;
        res[1]=-1;

        int left=0,right=nums.length-1;
        while (left<=right){
            int mid=(left+right)/2;
            if(nums[mid]>target){
                right=mid-1;
            }else if(nums[mid]<target){
                left=mid+1;
            }else {
                right=mid;
                left=mid;
                while (right<nums.length&&nums[right]==target){
                    right++;
                }
                while (left>=0&&nums[left]==target){
                    left--;
                }
                res[0]=left+1;
                res[1]=right-1;
                return res;
            }
        }
        return res;

    }


    public boolean canConstruct(String ransomNote, String magazine) {
        char[] a1 = ransomNote.toCharArray();
        char[] a2 = magazine.toCharArray();
        if(a2.length<a1.length){
            return false;
        }
        int[] aa = new int[26];
        for (int i = 0; i < a2.length; i++) {
             aa[a2[i]-'a']++;
        }
        for (int i = 0; i < a1.length; i++) {

            aa[a1[i]-'a']--;
            if(aa[a1[i]-'a']<0){
                return false;
            }
        }



        return true;

    }


    public int[] twoSum1(int[] nums, int target) {
        int[] res = new int[2];

        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int temp=target-nums[i];
            if (map.containsKey(temp)){
                res[0]=map.get(temp);
                res[1]=i;
                break;
            }
            map.put(nums[i],i);
        }
        return res;
    }

    public boolean isHappy(int n) {
        Set<Integer> record = new HashSet<>();
        while (n != 1 && !record.contains(n)) {
            record.add(n);
            n = getNextNumber(n);
        }
        return n == 1;
    }

    private int getNextNumber(int n) {
        int res =0;
        while (n>0){
            int temp=n%10;
            res+=temp*temp;
            n/=10;
        }
        return res;
    }

    public static int[] intersection(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int p=0,q=0;
        ArrayList<Integer> list = new ArrayList<>();
        while (p < nums1.length && q < nums2.length) {
            if(nums1[p]<nums2[q]){
                p++;
            }else if(nums1[p]>nums2[q]){
                q++;
            }else {
                if(list.contains(nums1[p])){

                }else {
                    list.add(nums1[p]);
                }
                p++;
                q++;
            }

        }
        int[] ints = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ints[i]=list.get(i);
        }
//        System.out.println(list);
        return ints;

    }

    public boolean isAnagram(String s, String t) {
        if(s.length()!=t.length())
            return false;
        char[] s1 = s.toCharArray();
        char[] s2 = t.toCharArray();

        int[] sum = new int[26];

        for (int i = 0; i < s1.length; i++) {
            sum[s1[i]-'a']++;
        }
        for (int i = 0; i < s2.length; i++) {
            sum[s2[i]-'a']--;
            if(sum[s2[i]-'a']<0){
                return false;
            }
        }
        return true;

    }


    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        int lenA=0,lenB=0;
        ListNode pa=headA;
        ListNode pb=headB;

        while (pa!=null){
            lenA++;
            pa=pa.next;
        }

        while (pb!=null){
            lenB++;
            pb=pb.next;
        }
        int dif=0;
        if(lenA>lenB){
            pa=headA;
            pb=headB;
            dif=lenA-lenB;
        }else {
            pa=headB;
            pb=headA;
            dif=lenB-lenA;
        }
        while (dif>0){
            dif--;
            pa=pa.next;
        }
        while (pa != null && pb != null) {
            if(pa==pb){
                return pa;
            }
            pa=pa.next;
            pb=pb.next;
        }



        return null;

    }


    public int lengthOfLongestSubstring(String s) {
        if (s.length()==0) {
            return 0;
        }
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max = 0;
        int left = 0;
        for(int i = 0; i < s.length(); i  ++){
            if(map.containsKey(s.charAt(i))){
                left = Math.max(left,map.get(s.charAt(i)) + 1);

            }
            map.put(s.charAt(i),i);
            max = Math.max(max,i-left+1);
        }
        return max;

    }


    public String reverseWords(String s) {
        char[] arr = s.toCharArray();
        int left=0,right=0;
        while (right<arr.length){
            if(arr[right]==' '){
                reverseString(arr, left, right-1);
                left=right+1;
            }
            right++;
        }
        reverseString(arr, left, right-1);

        return new String(arr);//把字符串数组变成字符串


    }

    public void reverseString(char[] s,int k,int j) {
        int left=k,right=j;
        while (left < right) {
            char temp=s[left];
            s[left]=s[right];
            s[right]=temp;
            left++;
            right--;
        }

    }

    public int[] twoSum(int[] numbers, int target) {
        int left=0,right=numbers.length-1;
        while (left<right){
            int sum=numbers[left]+numbers[right];
            if(sum>target){
                right--;
            }else if(sum<target){
                left++;
            }else {
                return new int[]{left+1,right+1};
            }
        }

        return new int[]{left+1,right+1};
    }

    public void moveZeroes(int[] nums) {
        int left=0,p=0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]!=0){
                int temp=nums[p];
                nums[p]=nums[i];
                nums[i]=temp;
                p++;
            }

        }

    }

    public int removeElement(int[] nums, int val) {
        int left=0,right=0;
        while (right < nums.length) {
            if(nums[right]!=val){
                nums[left]=nums[right];
                left++;
            }
            right++;
        }
        return left;
    }

    public void rotate(int[] nums, int k) {
        if(nums.length==1) return;
        reverse1(nums,0,nums.length);
        reverse1(nums,0,k);
       reverse1(nums,k,nums.length);


    }

    public void  reverse1(int[] nums ,int s,int k){
        int i=s,j=k-1;
        while(i<=j){
            int temp=nums[i];
            nums[i]=nums[j];
            nums[j]=temp;
            i++;
            j--;
        }

    }


    public int[] sortedSquares(int[] nums) {
        int left=0,right=nums.length-1;
        int arr[]=new int[nums.length];
        //int [ ] arr3=Arrays.copyOf(nums,nums.length);
        int p=nums.length-1;
        while(left<=right){
            int a=nums[left]*nums[left];
            int b=nums[right]*nums[right];
            if(a>b){
                arr[p--]=a;
                left++;
            }else {
                arr[p--]=b;
                right--;
            }
        }

        return arr;
    }

    public int searchInsert(int[] nums, int target) {
        int left=0,right=nums.length-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]>target){
                right=mid-1;
            }else if(nums[mid]<target){
                left=mid+1;
            }else {
                return mid;
            }
        }

        return left;
    }

    public int search(int[] nums, int target) {
        int mid;
        int i=0,j=nums.length-1;

        while (i <= j) {
            mid=(i+j)/2;
            if(nums[mid]<target){
                i=mid+1;
            }else if(nums[mid]>target){
                j=mid-1;
            }else {
                return  mid;
            }
        }

        return -1;

    }

    public static int [] res(int a[],int b[]){
        int c[]=new int[a.length+b.length];
        int i=0,j=0,k=0;
        while (i < a.length && j < b.length) {
            if(a[i]<=b[j]){
                c[k++]=a[i++];
            }else {
                c[k++]=b[j++];
            }
        }
        while(i<a.length){
            c[k++]=a[i++];
        }
        while(j<b.length){
            c[k++]=b[j++];
        }
        return c;
    }

    public static void reverse(int a[],int left,int right){
        while(left<right){
            int temp=a[left];
            a[left]=a[right];
            a[right]=temp;
            left++;
            right--;
        }
    }

    public static void findx(int a[],int x){
        int left=0,right=a.length-1;
        while (left<right){
            int mid=(left+right)/2;
            if(a[mid]==x){
                int temp=a[mid];
                a[mid]=a[a.length-1];
                a[a.length-1]=temp;
               break;
            }else if(a[mid]>x){
                right=mid-1;
            }else {
                left=mid+1;
            }
        }
        System.out.println(Arrays.toString(a));

    }

    public static int findMid(int a[],int b[]){
        int k=(a.length*2-1)/2;
        int c[]=new int[k+1];
        int p=0;
        int i=0,j=0;
        while (i<a.length&&j<b.length&&k>=0){
            if (a[i]<=b[j]){
                c[p++]=a[i];
                i++;
                k--;
            }else {
                c[p++]=b[j];
                j++;
                k--;
            }
        }
        System.out.println(Arrays.toString(c));
        return c[p-1];
    }

    public static int findM(int a[]){
        int n=a.length;
        int b[]=new int[n];
        for (int i = 0; i < n; i++) {
            b[a[i]]++;

        }
        int max=0;
        for (int i = 0; i < n; i++) {
            if (b[i]>max){
                max=b[i];
            }
        }
        if(max>n/2){
            return max;
        }else {
            return -1;
        }
    }

    public static int minIte(int a[]){
        int b[]=new int[a.length+2];
        for (int i = 0; i < a.length; i++) {
            if(a[i]<0||a[i]>a.length) continue;

            b[a[i]]++;
        }
        int min=-1;
        for (int i = 1; i < b.length; i++) {
            if (b[i]==0){
                min=i;
                break;
            }
        }
        return min;
    }

}

